package com.interview.javabase.algorithm;

/**
 * @author: zsg
 * @description: 插入排序法
 * @date: 2019/8/25 16:25
 * @modified:
 */
public class InsertSort {

    public static void main(String[] args) {
        Integer[] arr = new Integer[]{101, 34, 119, 1, -1, -2};

        for (int i = 0; i < arr.length - 1; i++) {

            // 待插入的数据
            int insetValue = arr[i + 1];

            // 待插入数据的前一个下标
            int insertIndex = i;

            // 满足下标大于等于0 且 待插入的数据小于 有序数组的某一个值 （说明还没有找出需要插入的数据的下标）
            // 需要将arr[insertIndex]往后挪
            while (insertIndex >= 0 && insetValue < arr[insertIndex]) {
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }

            // 此时需要将待插入值到 insertIndex + 1 位置
            arr[insertIndex + 1] = insetValue;

            for (int j = 0; j < arr.length; j++) {
                Integer integer = arr[j];
                System.out.print(integer + " ");
            }

            System.out.println();
        }
    }
}
